package com.googlecode.curvedmetromaps.core.model.importer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

public class EulerTrail {
	/** Undirected edges graph. */
	private HashMap<String, HashSet<String>>	edges;

	/** Subset of edges that are removed. */
	private HashMap<String, HashSet<String>>	removedEdges;

	private ArrayList<String>					trail;

	public EulerTrail(HashMap<String, HashSet<String>> edges) {
		removedEdges = new HashMap<String, HashSet<String>>();
		trail = new ArrayList<String>(edges.size() + 1);
		this.edges = edges;
		makeUndirected();
	}

	/**
	 * Computes an Euler trail using Fleury's algorithm in O(|E|^2).
	 */
	public ArrayList<String> getEulerTrail() {
		removedEdges.clear();
		trail.clear();

		if (edges.size() > 0) {
			// Find vertex with odd degree, the starting point for the trail.
			String oddStation = edges.keySet().iterator().next();
			for (Entry<String, HashSet<String>> entry : edges.entrySet()) {
				if (entry.getValue().size() % 2 != 0) {
					oddStation = entry.getKey();
					break;
				}
			}

			trail.add(oddStation);
			computeEulerTrail(oddStation);
		}

		return trail;
	}

	/**
	 * Recursive function that computes an Euler trail starting from u, given
	 * the sets 'edges' and 'removedEdges'.
	 * @param u The current vertex
	 */
	private void computeEulerTrail(String u) {
		for (String v : edges.get(u)) {
			if (isRemovedEdge(u, v) == false && isValidNextEdge(u, v)) {
				removeEdge(u, v);
				trail.add(v);
				computeEulerTrail(v);
			}
		}
	}

	/**
	 * Make edges graph undirected by adding all vertex pairs in reverse.
	 */
	private void makeUndirected() {
		// Make a copy of the keySet to avoid concurrent modification.
		HashSet<String> sources = new HashSet<String>(edges.keySet());
		for (String source : sources) {
			for (String target : edges.get(source)) {
				if (target.equals(source) == false) {
					if (edges.containsKey(target) == false)
						edges.put(target, new HashSet<String>());
					edges.get(target).add(source);
				}
			}
		}
	}

	/**
	 * Determines whether (u, v) is a valid next edge.
	 * @return true, if (u,v) is a valid next edge.
	 */
	private boolean isValidNextEdge(String u, String v) {
		// The edge u-v is valid in one of the following two cases:

		// 1) If v is the only adjacent vertex of u
		if (edges.get(u).size() == 1)
			return true;

		// 2) If there are multiple adjacents, then u-v is not a bridge
		// Do following steps to check if u-v is a bridge

		// 2.a) count of vertices reachable from u
		HashSet<String> reachable = new HashSet<String>();
		findReachableVertices(u, reachable);
		int count1 = reachable.size();

		// 2.b) Remove edge (u, v) and after removing the edge, count vertices
		// reachable from u
		removeEdge(u, v);
		findReachableVertices(u, reachable);
		int count2 = reachable.size();

		// 2.c) Add the edge back to the graph
		addEdge(u, v);

		// 2.d) If count1 is greater, then edge (u, v) is a bridge
		return (count1 > count2) ? false : true;
	}

	/**
	 * Adds (u, v) to edges and removes it from removedEdges.
	 * @param u the u
	 * @param v the v
	 */
	private void addEdge(String u, String v) {
		if (edges.get(u) == null)
			edges.put(u, new HashSet<String>());
		if (edges.get(v) == null)
			edges.put(v, new HashSet<String>());
		edges.get(u).add(v);
		edges.get(v).add(u);

		if (removedEdges.get(u) != null)
			removedEdges.get(u).remove(v);
		if (removedEdges.get(v) != null)
			removedEdges.get(v).remove(u);
	}

	/**
	 * Adds (u, v) to removedEdges and leaves edges unchanged.
	 * @param u the u
	 * @param v the v
	 */
	private void removeEdge(String u, String v) {
		if (removedEdges.get(u) == null)
			removedEdges.put(u, new HashSet<String>());
		if (removedEdges.get(v) == null)
			removedEdges.put(v, new HashSet<String>());
		removedEdges.get(u).add(v);
		removedEdges.get(v).add(u);
	}

	private boolean isRemovedEdge(String u, String v) {
		return removedEdges.containsKey(u) && removedEdges.get(u).contains(v);
	}

	/**
	 * Computes the set of all reachable vertices.
	 * @param v Vertex from which to start
	 * @param reachable After call completes this will contain the reachable
	 *            vertices.
	 */
	private void findReachableVertices(String v, HashSet<String> reachable) {
		reachable.add(v);
		for (String u : edges.get(v)) {
			if (reachable.contains(u) == false) {
				findReachableVertices(u, reachable);
			}
		}
	}

}
